# source:https://leetcode.cn/problems/closest-dessert-cost/ 0/1背包 DP
from functools import cache
from math import inf
from typing import List

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        # 先检查基料是否有直接达到或超过 target 的
        min_base = min(baseCosts)
        if min_base >= target:
            return min_base
        
        closest = float('inf')  # 记录最接近 target 的成本
        
        for base in baseCosts:
            # 创建 DP 数组，dp[i][j] 表示前 i 种配料是否能组合出价格 j
            dp = [[False] * (2 * target + 1) for _ in range(len(toppingCosts) + 1)]
            if base < 2*target+1:
                dp[0][base] = True  # 仅基料的初始状态
            
            for i in range(len(toppingCosts)):
                topping = toppingCosts[i]
                for cost in range(2 * target + 1):  # 遍历所有可能的花费
                    if dp[i][cost]:  # 如果前 i-1 种配料可以组成 cost
                        dp[i+1][cost] = True  # 不选当前配料
                        if cost + topping <= 2 * target:
                            dp[i+1][cost + topping] = True  # 选 1 份
                        if cost + 2 * topping <= 2 * target:
                            dp[i+1][cost + 2 * topping] = True  # 选 2 份
            
            # 找最接近 target 的值
            for cost in range(2 * target + 1):
                if dp[len(toppingCosts)][cost]:  # 该成本可达
                    if abs(cost - target) < abs(closest - target) or \
                       (abs(cost - target) == abs(closest - target) and cost < closest):
                        closest = cost
        
        return closest

# 法二: 记忆化搜索
class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        # 小优化：将基料和配料排序后，从大到小搜索，可以快速减枝
        baseCosts.sort()
        toppingCosts.sort()
        res = inf

        # i: 第i个配料: 选一份、选两份、不选
        # ssm: 当前的花费
        @cache
        def dfs(i, ssm):
            nonlocal res
            # 就这一处剪枝
            if ssm - target > abs(res - target):
                return
            
            # 这里不停更新res，也是加速后续剪枝
            if abs(ssm - target) < abs(res - target):
                res = ssm
            # 有多种方案，返回 成本相对较低 的一种
            if abs(ssm - target) == abs(res - target):
                res = min(res, ssm)
            # 选一份、选两份、不选
            for j in range(i, -1, -1):
                dfs(j - 1, ssm + toppingCosts[j])
                dfs(j - 1, ssm + 2 * toppingCosts[j])
                dfs(j - 1, ssm)

        for x in baseCosts[::-1]:
            dfs(len(toppingCosts) - 1, x)
        return res

# source:https://leetcode.cn/problems/largest-sum-of-averages/ 划分型DP 记忆化搜索
class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        @cache
        def dfs(i, cnt):
            if cnt == 0:
                if i < 0:
                    return 0
                return -inf
            if i < 0:
                return -inf 
            res = -inf
            # divide
            for j in range(i+1):
                res = max(res, dfs(j-1, cnt-1) + (pre[i+1] - pre[j])/(i - j + 1))
            return res
        pre = [0]
        for v in nums:
            pre.append(pre[-1] + v)
        return dfs(len(nums)-1, k)
